package phaseIref;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class NFA {
	private State start;
	private State accept;
	HashMap<String, Integer> priorityMap;  //For token generation



	/**
	 * Constructor for NFA
	 * @param start the start state
	 * @param accept the accept state
	 */
	public NFA(State start, State accept) {
		this.start = start;
		this.accept = accept;

	}

	public boolean testString(String s) {

		Set<State> curStates, newStates, temp;
		curStates = new HashSet<State>();
		curStates.add(start);
		temp = new HashSet<State>();
		newStates = new HashSet<State>();
		char[] arr = s.toCharArray();
		for(char c : arr) {
			//Get epsilon closure for every state
			for(State state : curStates) {
				temp.addAll(state.epsilonClosure());
			}

			curStates = temp;
			//For every state, add the transitions from the character
			for(State state : curStates) {
				if(state.transition(c) != null)
					newStates.addAll(state.transition(c));
			}
			curStates = newStates;
			newStates = new HashSet<State>();
			temp.clear();
		}
		//Check the epsilon closure of every state to see if we have succeeded
		for(State state : curStates) 
			for(State ep : state.epsilonClosure()) {
				if(ep.isAccept())
					return true;
			}
		return false;
	}

	/**
	 * BONUS PART
	 * Given a scanner, tokenize the strings in the scanner.
	 * @param s the scanner
	 */
	public void tokenize(Scanner s) {
		int max = 0, num = 0;
		int[] tmp = new int[2];
		
		while(s.hasNextLine()) {
			tmp = tokenizeLine(s.nextLine());
			max = Math.max(max, tmp[1]);
			num += tmp[0];
		}
		System.out.println(num + " total transitions.\n" + max + " maximum clones seen at once.");
	}
	
	/**
	 * BONUS PART
	 * Tokenize one line using this NFA
	 * @param s the line to tokenize
	 * @return an array with the number of total transitions made, and the max number of clones seen.
	 */
	public int[] tokenizeLine(String s) {

		Set<State> curStates, newStates, temp;
		int lastAcceptInd = -1;
		String lastAcceptToken = "";
		curStates = new HashSet<State>();
		curStates.add(start);
		temp = new HashSet<State>();
		newStates = new HashSet<State>();
		int numTransitions = 0;
		int maxClones = 0;
		int i = 0;
		int j = 0;
		boolean found;
		
		while(i < s.length()) {
			//Get epsilon closure for every state
			for(State state : curStates) {
				temp.addAll(state.epsilonClosure());
			}
			curStates = temp;
			//For every state, add the transitions from the character
			for(State state : curStates) {
				numTransitions += state.transition(s.charAt(i)).size();
				newStates.addAll(state.transition(s.charAt(i)));
			}
			maxClones = Math.max(maxClones, newStates.size());
			if(newStates.isEmpty() || i == s.length()-1) { //Failed, let's clean up.
				found = false;
				if(!newStates.isEmpty() && i == s.length() - 1) {
					i++;
					curStates = newStates;
					newStates = new HashSet<State>();
				}
				String token = "";
				int priority = Integer.MAX_VALUE;
				for(State state : curStates) {
					for(State ep : state.epsilonClosure()) {
						if(ep.isAccept()) {
							if(priority > priorityMap.get(ep.getToken())) {
								token = ep.getToken();
								priority = priorityMap.get(ep.getToken());
							}
							found = true;
						}
					}
				}
				if(!found) { //We weren't in an accept state
					if(lastAcceptInd != -1) {  //But we've seen one, so let's fall back there.
						i = lastAcceptInd;
						System.out.println(s.substring(j, i) + " " + lastAcceptToken.substring(1));
						j = i;
						lastAcceptToken = "";
						lastAcceptInd = -1;
					} else { //We failed entirely, skip this character.
						j = i+1;
					}
					newStates.clear();
					newStates.add(start);
				} else {
					System.out.println(token.substring(1) + " " + s.substring(j, i));
					j = i;
					if(j != s.length() || j != i)
						i--;
					newStates.clear();
					newStates.add(start);
					lastAcceptToken = "";
					lastAcceptInd = -1;
				}
				numTransitions++;
			} else {
				int priority = Integer.MAX_VALUE;
				String token = "";
				for(State state : curStates) 
					for(State ep : state.epsilonClosure()) {
						if(ep.isAccept()) {
							if(priority > priorityMap.get(ep.getToken())) {
								token = ep.getToken();
								priority = priorityMap.get(ep.getToken());
							}
							lastAcceptInd = i;
							lastAcceptToken = token;
						}
					}
			}

			curStates = newStates;
			newStates = new HashSet<State>();
			temp.clear();


			i++;
		}
		
		
		//System.out.println(numTransitions + " total transitions.\n" + maxClones + " maximum clones seen at once.");
		return new int[] {numTransitions, maxClones};
	}

	public static NFA epsilonNFA() {
		State start = new State(false);
		State accept = new State(true);
		start.addEpsilonTransition(accept);
		return new NFA(start, accept);
	}

	/**
	 * Union the given NFAs
	 * @param nfas the NFAs to union 
	 * @return the NFA with an epsilon transition to all of the nfas in the given input
	 */
	public static NFA union(NFA... nfas) {
		State start = new State(false);
		State accept = new State(true);
		for(NFA n : nfas) {
			start.addEpsilonTransition(n.getStart());
			n.getAccept().addEpsilonTransition(accept);
			n.getAccept().setAccept(false);
		}

		return new NFA(start, accept);
	}

	/**
	 * Union the given NFAs together, but leave their accept states alone (don't generate a new accept state and epsilon transition to it).
	 * Used for the final step of NFA construction, so we can tokenize properly.
	 * @param nfas the NFAs to union
	 * @return a union of the given NFAs
	 */
	public static NFA unionNoEpsilon(NFA... nfas) {
		State start = new State(false);
		for(NFA n : nfas) {
			start.addEpsilonTransition(n.getStart());
		}

		return new NFA(start, null);
	}

	/**
	 * Concatenate the two NFAs together by adding an epsilon transition from the end of a to the beginning of b
	 * @param a the first NFA
	 * @param b the second NFA
	 * @return the concatenation of a and b
	 */
	public static NFA concatenate(NFA a, NFA b) {
		a.getAccept().addEpsilonTransition(b.getStart());
		a.getAccept().setAccept(false);
		return new NFA(a.getStart(), b.getAccept());
	}

	/**
	 * Apply the Kleene star to the given NFA
	 * @param a the NFA to star
	 * @return the Kleene star of the given NFA (a*)
	 */
	public static NFA star(NFA a) {
		State start = new State(false);
		State accept = new State(true);
		a.getAccept().setAccept(false);
		a.getAccept().addEpsilonTransition(a.getStart());
		a.getAccept().addEpsilonTransition(accept);
		start.addEpsilonTransition(accept);
		start.addEpsilonTransition(a.getStart());
		return new NFA(start, accept);
	}
	
	

	public State getStart() {
		return start;
	}

	public void setStart(State start) {
		this.start = start;
	}

	public State getAccept() {
		return accept;
	}

	public void setAccept(State accept) {
		this.accept = accept;
	}
	
	public HashMap<String, Integer> getPriorityMap() {
		return priorityMap;
	}

	public void setPriorityMap(HashMap<String, Integer> priorityMap) {
		this.priorityMap = priorityMap;
	}


	public String toString() {
		return start.toString();
	}


}
